\section{Related Work}
\label{sec:related}

The combination of an orienteering solver and a refinement search
planner was first described in \cite{Smith04}. Our approach differs by
using local search to solve the orienteering problem coupled with a
cost estimation method based on a distance graph. In contrast,
\cite{Smith04} uses a plan-graph based technique for cost estimation
and beam-search to solve the orienteering problem. The distance graph
is very appealing in our domain because of the strong dominance of
navigation in time and energy consumption.

Our work is further discriminated as it is used on-board an AUV rather
than off-board for Mars Rovers. To our knowledge, no over-subscription
planning technique has been applied in underwater robotics.
